% o  Large
%     o  par-dd
%         Aqui, divide-se o texto pré-processado entre todos os processos (sem
%         quebrar palavras no meio) para então acharem os palíndromos. Depois se
%         envia os palíndromos para um único processo que remove os repetidos e
%         imprime todos, junto com o resultado da primalidade soma dos dígitos.
%
%         Talvez fazer o crivo distribuído e enviar de volta não só os
%         palíndromos mas também os primos calculados por cada um.
%     o  par-dnc
%         Um único processo preprocessa todo o texto, removendo as palavras
%         repetidas, após isso, este processo envia (on demand) blocos de palavras
%         para cada um dos outros processos fazerem o trabalho de procurar
%         palíndromos, verificar a primalidade e imprimir os resultados.
%
% o  Small
%     o  par
%     o  seq

% Exemplo de relatório técnico do IC

% Criado por P.J.de Rezende antes do Alvorecer da História.
% Modificado em 97-06-15 e 01-02-26 por J.Stolfi.
% modificado em 2003-06-07 21:12:18 por stolfi
% modificado em 2008-10-01 por cll
% \def\lastedit{2010-03-16 17:56:58 by stolfi}

\nonstopmode % PARA RODAR LATEX EM BATCH MODE
\documentclass[11pt,twoside]{article}

\usepackage{techrep-ic}

%%% SE USAR INGLÊS, TROQUE AS ATIVAÇÕES DOS DOIS COMANDOS A SEGUIR:
\usepackage[brazil]{babel}
%% \usepackage[english]{babel}

%%% SE USAR CODIFICAÇÃO LATIN1 OU UTF-8, ATIVE UM DOS DOIS COMANDOS A
%%% SEGUIR:
%%\usepackage[latin1]{inputenc}
\usepackage[utf8]{inputenc}

%%% Para obter o tamanho de texto recomendado:
\usepackage[margin=1in]{geometry}

%%% Para simbolos de math
\usepackage{amsmath,amssymb,amsfonts,latexsym}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subcaption}
\usepackage{color}
\usepackage{multirow}
\usepackage{url}

\definecolor{gray}{gray}{0.95}

\lstset{
  backgroundcolor=\color{gray},
  basicstyle=\ttfamily,
  breaklines=true,
  captionpos=b,
  columns=fixed,
  language=sh,
  showstringspaces=false,
  tabsize=2
}

\begin{document}

%%% PÁGINA DE CAPA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Número do relatório
\TRNumber{02}

% DATA DE PUBLICAÇÃO (PARA A CAPA)
%
\TRYear{13} % Dois dígitos
\TRMonth{05} % Numérico, 01-12

% LISTA DE AUTORES PARA CAPA (sem afiliações).
\TRAuthor{R.A.Q. Cruz \and S.G. Fadel \and F.A. Neto}

% TÍTULO PARA A CAPA (use \\ para forçar quebras de linha).
\TRTitle{Desempenho de algoritmos paralelos para encontrar palíndromos}

\TRMakeCover

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% O que segue é apenas uma sugestão - sinta-se à vontade para
% usar seu formato predileto, desde que as margens tenham pelo
% menos 25mm nos quatro lados, e o tamanho do fonte seja pelo menos
% 11pt. Certifique-se também de que o título e lista de autores
% estão reproduzidos na íntegra na página 1, a primeira depois da
% página de capa.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nomes de autores ABREVIADOS e titulo ABREVIADO,
% para cabeçalhos em cada página.
%
\markboth{Cruz, Fadel e Neto}{Desempenho de algoritmos paralelos para encontrar palíndromos}
\pagestyle{myheadings}
\thispagestyle{empty}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TÍTULO e NOMES DOS AUTORES, completos, para a página 1.
% Use "\\" para quebrar linhas, "\and" para separar autores.
%
\title{Desempenho de algoritmos paralelos para encontrar palíndromos}

\author{Rommel Anatoli Quintanilla Cruz \and Samuel Gomes Fadel \and Filipe
Alves Neto}

\date{}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{abstract}

Apesar da facilidade em verificar se determinada palavra é um palíndromo, fazer
isso em um texto muito grande é um desafio. Este trabalho é parte da disciplina
de Programação Concorrente do ICMC/USP com o objetivo de avaliar o ganho de
desempenho com a paralelização destas tarefas. Concluímos que apesar de
altamente paralelizáveis, devido à simplicidade da operação e tamanho dos textos
utilizados, a sobrecarga gerada para o gerenciamento dos processos e threads
superam o ganho efetivo do paralelismo.

\end{abstract}

\section{Introdução}
Um palíndromo é uma sequência simétrica de caracteres ao redor de um centro.
Embora muitas vezes são vistos só como curiosidades alfabéticas, eles são
nomeadas em estudos de linguagens formais, biologia molecular, teoria da
computação, entre outros. Verificar se uma cadeia é igual ao seu reverso é
trivial, no entanto quando se quer fazer isso sob um texto fonte que tem milhões
de caracteres é um verdadeiro desafio. Desse modo, surge a necessidade de
decompor os dados para seu processamento. Neste trabalho foi usado paralelismo
tanto ao nível de memória compartilhada com OpenMP quanto ao nível de memória
distribuída com MPI. Este trabalho foi desenvolvido como parte do curso SC0143 -
Programação Concorrente do Instituto de Ciências Matemáticas e de Computação
(ICMC) da Universidade de São Paulo (USP).

\section{Objetivos}

Neste trabalho, objetiva-se avaliar os ganhos de desempenho com a paralelização
de tarefas. Para um texto pequeno, a tarefa é encontrar todas as palavras
palíndromas e, além disso, encontrar frases palíndromas. Uma frase palíndroma é
a maior sequência de letras (que formam uma palavra ou não) que é igual à
sequência contrária. Para um texto grande, a tarefa é encontrar todas as
palavras palíndromas e determinar se a soma do valor numérico de seus caracteres
é um número primo utilizando o crivo de Eratóstenes~\cite{sieve}.

\section{Implementação}

Os programas foram implementados utilizando a linguagem de programação C e, nas
versões paralelas, a implementação OpenMP do
gcc~\footnote{\url{http://gcc.gnu.org/wiki/openmp}} e a biblioteca Open
MPI~\footnote{\url{http://www.open-mpi.org/}}.

Os códigos dos programas desenvolvidos estão hospedados no repositório do Google
Code~\footnote{\url{https://code.google.com/p/pc2013-grupo06-turmab/}}. As soluções
para o problema do texto pequeno de forma sequencial e paralela estão,
respectivamente, nas pastas t2/small/seq e t2/small/par. Para o texto grande,
foram desenvolvidas três versões da solução: sequencial (t2/large/seq), paralela
utilizando decomposição recursiva ou dividir para conquistar (t2/large/par-dnc)
e paralela utilizando decomposição de dados (t2/large/par-dd).

\subsection{Texto Grande}

\subsubsection{Sequencial}
A solução do problema do texto grande de forma sequencial, primeiramente, abre o
arquivo que contém as palavras, calcula seu tamanho e armazena todo o texto na
memória. Em seguida, são calculados os números primos através do crivo de
Eratóstenes. Então, para cada palavra encontrada no texto, caso esta seja um
palíndromo e não seja repetida, o programa imprime a palavra, a soma dos códigos
ASCII de suas letras e se esta soma é um número primo ou não. Para decidir se
uma palavra é repetida ou não, o programa utiliza uma árvore AVL que armazena as
palavras encontradas.

\subsubsection{Paralelo -- Dividir para Conquistar}
Nesta solução, um dos processos, chamado de \textbf{root}, fica responsável por
dividir o problema original em problemas menores e os enviar para os demais
processos.

Na etapa de divisão, assim como na solução sequencial, o arquivo é copiado para
a memória. Com o arquivo em memória, a divisão das tarefas é feita através da
simulação de um pipeline de três estágios utilizando OpenMP:

\begin{itemize}
    \item Primeiro estágio: Substitui símbolos por espaços e torna todas as
        letras minúsculas;
    \item Segundo estágio: Localiza os começos e fim das palavras;
    \item Terceiro estágio: Remove palavas repetidas utilizando uma árvore AVL e
        distribui as tarefas pros demais processos.
\end{itemize}

Os demais processos, ao receberem as palavras que devem processar, verificam se
estas são palíndromos, calculam a soma dos códigos ASCII das letras de cada uma
das palavras e decidem se estas somas são números primos utilizando o crivo de
Eratóstenes.

A seguir, na Figura~\ref{fig:GrandeDC}, pode-se ver o funcionamento do
algoritmo.

\begin{figure}[h]
  \centering
  \includegraphics[width=0.5\linewidth]{img/large-dnc.eps}
  \caption{Diagrama de funcionamento da abordagem usando divisão e conquista.}
  \label{fig:GrandeDC}
\end{figure}

\subsubsection{Paralelo -- Decomposição de dados}
Neste método para divisão das tarefas, define-se um processo principal (aqui
denominado \textbf{root}). O processo root fica responsável pelo
pré-processamento do arquivo, que consiste em remover todos os caracteres que
não sejam letras maiúsculas, letras minúsculas e números. Depois, o arquivo é
dividido de modo que cada processo pegue aproximadamente a mesma quantidade de
dados para processar, mas sem quebrar palavras ao meio, para não perder
possíveis palíndromos. Em seguida, os pedaços são enviados aos outros processos
e, enquanto os outros processam os pedaços do arquivo, o root passa a executar o
crivo de Eratóstenes.

Em cada processo, os dados recebidos são quebrados em palavras, considerando
como palavra qualquer sequência contígua de 3 ou mais caracteres que não sejam
espaços em branco. Determina-se então se a palavra é palíndroma e, se for, ela é
enviada ao processo root.

De volta ao root, cada palavra recebida é colocada em uma árvore binária de
busca, de modo a identificar rapidamente as palavras repetidas. Então, depois de
obter a lista de todas as palavras, o processo root as imprime, juntamente com a
soma de seus caracteres e um ``sim'' ou ``não'' indicando se esta soma é um
número primo ou não.

A seguir, na Figura~\ref{fig:GrandeDD}, pode-se ver o funcionamento do
algoritmo.

\begin{figure}[h]
  \centering
  \includegraphics[width=0.7\linewidth]{img/large-dd.eps}
  \caption{Diagrama de funcionamento da abordagem usando decomposição de dados.}
  \label{fig:GrandeDD}
\end{figure}

\subsection{Texto Pequeno}

\subsubsection{Sequencial}
Na versão sequencial, em primeiro lugar, o texto todo é carregado na memória, e antes de
começar a busca por palíndromos, apaga-se qualquer carácter não alfabético na fase de
pré-processamento, de tal maneira que se deixam só palavras separadas por um único espaço.
Foi implementado um algoritmo de força bruta que consiste em percorrer carácter por
carácter à procura de palíndromos com centro em cada carácter da cadeia preprocessada,
primeiramente de tamanho par e depois de tamanho ímpar. Finalmente de acordo com a
definição do problema, somente são impressas as cadeias palíndromas cujas letras limites
sejam espaços.

\subsubsection{Paralelo}
Para o caso da versão paralela, o objetivo foi ter cuidado ao ignorar possíveis respostas
quando a divisão de dados é disjunta. Logo foi implementada a abordagem de divisão de
dados com um ajustamento, toda a cadeia enviada a cada outro processo, mas cada processo é
responsável por um intervalo próprio segundo seu id de processo. Assim, o processo root é
o responsável por fazer o pré-processamento e enviar a todos os demais nós todo o texto.
Cada nó procura palíndromos da mesma maneira do que a versão paralela.

A seguir, na Figura~\ref{fig:PequenoParalelo}, pode-se ver o funcionamento do
algoritmo.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.6\linewidth]{img/small-par.eps}
    \caption{Diagrama de funcionamento do algoritmo paralelo para o texto
    pequeno.}
    \label{fig:PequenoParalelo}
\end{figure}

\section{Resultados}

A seguir estão os resultados de desempenho do texto pequeno e do texto grande,
tanto para a abordagem de divisão e conquista quanto para a abordagem de divisão
de dados. Todos os tempos são determinados como uma média de três execuções
diferentes e com um intervalo de confiança de $95\%$.

\begin{table}[h!]
    \centering
    \begin{tabular}{ c c c c c c}
        \hline
        T. Sequencial (ms) & N. Processos & T. Paralelo$^1$ (ms) & Speedup$^1$ & T. Paralelo$^2$ (ms) & Speedup$^2$ \\ \hline
        \hline
        \multirow{4}{*}{170$\pm$4} & 2 &  204$\pm$1  & 0.83 &  915$\pm$73  & 0.19 \\
                                   & 3 &  174$\pm$13 & 0.97 & 1080$\pm$142 & 0.16 \\
                                   & 4 &  204$\pm$9  & 0.83 & 1466$\pm$70  & 0.12 \\
                                   & 5 & 1206$\pm$11 & 0.14 & 1433$\pm$73  & 0.12 \\ \hline
    \end{tabular}
    \caption{Tempo de execução e speedup para texto pequeno. (1) Utilizando um único nó.
    (2) Utilizando mais de um nó.}
    \label{tab:SpeedupPequeno}
\end{table}

\begin{table}[h!]
    \centering
    \begin{tabular}{ c c c c c c}
        \hline
        T. Sequencial (ms) & N. Processos & T. Paralelo$^1$ (ms) & Speedup$^1$ & T. Paralelo$^2$ (ms) & Speedup$^2$ \\ \hline
        \hline
        \multirow{4}{*}{379$\pm$14} & 2 &  8767$\pm$1176  & 0.04 & 12968$\pm$925   & 0.03 \\
                                    & 3 &  8812$\pm$198   & 0.04 & 13743$\pm$2012  & 0.03 \\
                                    & 4 &  9156$\pm$103   & 0.04 & 13105$\pm$472   & 0.03 \\
                                    & 5 & 11442$\pm$392   & 0.03 & 14040$\pm$1257  & 0.03 \\ \hline
    \end{tabular}
    \caption{Tempo de execução e speedup para o texto grande usando a abordagem dividir
    para conquistar. (1) Utilizando um único nó. (2) Utilizando mais de um nó.}
    \label{tab:SpeedupGrandeDnC}
\end{table}

\begin{table}[h!]
    \centering
    \begin{tabular}{ c c c c c c}
        \hline
        T. Sequencial (ms) & N. Processos & T. Paralelo$^1$ (ms) & Speedup$^1$ & T. Paralelo$^2$ (ms) & Speedup$^2$ \\ \hline
        \hline
        \multirow{4}{*}{379$\pm$14} & 2 & 1083$\pm$12 & 0.35 & 2314$\pm$62  & 0.16 \\
                                    & 3 &  761$\pm$26 & 0.50 & 2162$\pm$207 & 0.18 \\
                                    & 4 &  666$\pm$42 & 0.57 & 2281$\pm$87  & 0.17 \\
                                    & 5 & 1653$\pm$6  & 0.23 & 2237$\pm$126 & 0.17 \\ \hline
    \end{tabular}
    \caption{Tempo de execução e speed para o texto grande utilizando decomposição de
    dados. (1) Utilizando um único nó. (2) Utilizando mais de um nó.}
    \label{tab:SpeedupGrandeDD}
\end{table}

Nas Figuras~\ref{fig:TempoPequeno},~\ref{fig:TempoGrandeDnC}
e~\ref{fig:TempoGrandeDD}, são comparados os tempos de execução da versão
sequencial e paralela de cada um dos problemas e abordagem.

\begin{figure}[h]
    \centering
    \includegraphics[width=0.95\linewidth]{img/small-tempos.eps}
    \caption{Tempos de execução para o texto pequeno.}
    \label{fig:TempoPequeno}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.95\linewidth]{img/large-dnc-tempos.eps}
    \caption{Tempos de execução para o texto grande na abordagem de dividir para
    conquistar.}
    \label{fig:TempoGrandeDnC}
\end{figure}

\begin{figure}[h]
    \centering
    \includegraphics[width=0.95\linewidth]{img/large-dd-tempos.eps}
    \caption{Tempos de execução para o texto grade na abordagem de decomposição
    de dados.}
    \label{fig:TempoGrandeDD}
\end{figure}

\section{Conclusões}

Para ambos os problemas, percebeu-se que as versões sequenciais para a solução
são mais eficientes que as versões paralelas. Isto acontece, principalmente,
porque a sobrecarga gerada para gerenciar as múltiplas threads ou múltiplos
processos é maior que ganho de desempenho, uma vez que as versões sequenciais
são muito rápidas, rodando em média em 170 e 379 milissegundos para o texto
pequeno e grande, respectivamente.

No geral, estes problemas são altamente paralelizáveis, logo se a tarefa fosse
mais custosa, por exemplo um texto muito maior ou operações mais complexas, o
ganho de desempenho ultrapassaria a sobrecarga das bibliotecas utilizadas.

\bibliographystyle{abnt}
\bibliography{relatorio}

\end{document}
